package graphclustering.util;

import graphclustering.data.Cluster;
import graphclustering.data.DWGraph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;

public class ClusteringUtils {

	public static String seperator = "-";

	public static int maxConsideredNeighborNodeNum = 10;

	public static int maxConsideredClusterNumForOneNode = 100;

	// Select candidate clusters for a give node i in the graph
	public static List<Cluster> selectClusterCandidateforOneNode(DWGraph graph,
			int index, int maxNodeNum) {
		// Initiate the candidateClusterList
		List<Cluster> candidateClusterList = new ArrayList<Cluster>();

		// Get all possible clusters by enumerate the direct-neighbor node of
		// the index node
		List<String> firstNeighborNodeIDList = getNeighborNodeIDListFor(
				graph.nodeIDList.get(index), graph);
		// if(graph.nodeSize==6){
		// System.out.println(firstNeighborNodeIDList);
		// System.out.println(graph.graph);
		// }
		List<Cluster> firstCircle = getAllPossibleCombination(
				firstNeighborNodeIDList, maxNodeNum - 1);

		/*
         * //For each cluster in the first circle cluster, //Get all possible
         * clusters by enumerate the direct-neighbor node of the nodes in the
         * tmp cluster for (Cluster tmp: firstCircle) { List<String>
         * secondNeighborNodeIDList =
         * getNeighborNodeIDListFor(tmp.atomicNodeIDList,graph); List<String>
         * existingNodeIDList = new ArrayList<String>();
         * existingNodeIDList.add(graph.nodeIDList.get(index));
         * existingNodeIDList.addAll(tmp.atomicNodeIDList);
         * deleteOverlapNodeIDs(secondNeighborNodeIDList, existingNodeIDList);
         * deleteOverlapNodeIDs(secondNeighborNodeIDList,
         * firstNeighborNodeIDList); List<Cluster> secondCircle =
         * getAllPossibleCombination(secondNeighborNodeIDList, maxNodeNum-2);
         * addExistingNodeIDsFor(secondCircle, existingNodeIDList);
         * candidateClusterList.addAll(secondCircle); }
         */

		List<String> existingNodeIDList = new ArrayList<String>();
		existingNodeIDList.add(graph.nodeIDList.get(index));
		addExistingNodeIDsFor(firstCircle, existingNodeIDList);
		candidateClusterList.addAll(firstCircle);

		// Cluster oneNodeCluster = new Cluster();
		// oneNodeCluster.atomicNodeIDList.add(graph.nodeIDList.get(index));
		// candidateClusterList.add(oneNodeCluster);

		if (candidateClusterList.size() > maxConsideredClusterNumForOneNode) // Maybe
		// rodomly
		// select
		// 200
		// candidates
		// here
		{
			Random random = new Random();
			random.setSeed(candidateClusterList.size());

			List<Cluster> newCandidateClusterList = new ArrayList<Cluster>();
			for (int i = 0; i < maxConsideredClusterNumForOneNode; i++) {
				float rIndex = java.lang.Math.abs((((float) random.nextInt()))
						/ ((float) java.lang.Integer.MAX_VALUE))
						* candidateClusterList.size();
				newCandidateClusterList.add(candidateClusterList
						.get((int) rIndex));
			}
			return newCandidateClusterList;
		} else
			return candidateClusterList;

	}

	// Get neighbor node id list for a given nodeID in the graph
	public static List<String> getNeighborNodeIDListFor(String nodeID,
			DWGraph graph) {
		List<String> neighborNodeIDList = new ArrayList<String>();
		List<Float> imValueList = new ArrayList<Float>();

		int index = graph.nodeIDList.indexOf(nodeID);

		for (int i = 0; i < graph.nodeIDList.size(); i++) {
			if (graph.graph[index][i] > 0.00000001 && index != i) {
				String neighborNodeID = graph.nodeIDList.get(i);
				if (!neighborNodeIDList.contains(neighborNodeID)) {
					neighborNodeIDList.add(neighborNodeID);
					imValueList.add(new Float(graph.graph[index][i]));
				}
			} else if ((graph.graph[i][index] > 0.000000001 && index != i)) {
				String neighborNodeID = graph.nodeIDList.get(i);
				if (!neighborNodeIDList.contains(neighborNodeID)) {
					neighborNodeIDList.add(neighborNodeID);
					imValueList.add(new Float(graph.graph[i][index]));
				}
			}
		}

		if (neighborNodeIDList.size() > maxConsideredNeighborNodeNum) {
			for (int i = 0; i < neighborNodeIDList.size(); i++) {
				float currBiggestIMValue = imValueList.get(i).floatValue();
				int currBiggestIndex = i;
				for (int j = i + 1; j < neighborNodeIDList.size(); j++) {
					if (imValueList.get(j).floatValue() > currBiggestIMValue) {
						currBiggestIndex = j;
						currBiggestIMValue = imValueList.get(j).floatValue();
					}
				}
				if (currBiggestIndex != i) {
					Float currBiggestIM = imValueList.get(currBiggestIndex);
					String currBiggestNode = neighborNodeIDList
							.get(currBiggestIndex);
					neighborNodeIDList.set(currBiggestIndex, neighborNodeIDList
							.get(i));
					imValueList.set(currBiggestIndex, imValueList.get(i));
					neighborNodeIDList.set(i, currBiggestNode);
					imValueList.set(i, currBiggestIM);
				}
			}
			while (neighborNodeIDList.size() > maxConsideredNeighborNodeNum) {
				int size = neighborNodeIDList.size();
				neighborNodeIDList.remove(size - 1);
			}

		}

		// eniminateDuplica(neighborNodeIDList);
		return neighborNodeIDList;

	}

	// Get neighbor node id list for a given candidateNodeIDList in the graph
	public static List<String> getNeighborNodeIDListFor(
			List<String> candidateNodeIDList, DWGraph graph) {
		List<String> neighborNodeIDList = new ArrayList<String>();

		for (String tmpNodeID : candidateNodeIDList) {
			neighborNodeIDList
					.addAll(getNeighborNodeIDListFor(tmpNodeID, graph));
		}

		eniminateDuplica(neighborNodeIDList);
		return neighborNodeIDList;
	}

	// Delete overlapped node ids from candidateNodeIDList based on comparison
	// with existingNodeIDList
	public static void deleteOverlapNodeIDs(List<String> candidateNodeIDList,
			List<String> existingNodeIDList) {
		for (String existNodeID : existingNodeIDList) {
			int index = candidateNodeIDList.indexOf(existNodeID);
			if (index >= 0) {
				candidateNodeIDList.remove(index);
			}
		}
	}

	public static void addExistingNodeIDsFor(
			List<Cluster> candidateClusterList, List<String> existingNodeIDList) {
		for (Cluster tempCluster : candidateClusterList) {
			tempCluster.atomicNodeIDList.addAll(existingNodeIDList);
		}
	}

	public static List<Cluster> getAllPossibleCombination(
			List<String> nodeIDList, int maxSize) {
		List<Cluster> clusterList = new ArrayList<Cluster>();
		;

		for (int size = 1; size <= nodeIDList.size() && size < maxSize; size++) {
			clusterList.addAll(getPossibleSizedCombination(nodeIDList, size));
		}

		return clusterList;
	}

	// Get all possible combinations in a list whose size is a given number
	private static List<Cluster> getPossibleSizedCombination(
			List<String> nodeIDList, int size) {
		if (size > nodeIDList.size() || size <= 0)
			return null;

		List<Cluster> clusterList = new ArrayList<Cluster>();

		if (size == 1) {
			for (String tmp : nodeIDList) {
				Cluster tempC = new Cluster();
				tempC.atomicNodeIDList.add(tmp);
				clusterList.add(tempC);
			}
			return clusterList;
		}

		for (String tmp : nodeIDList) {
			List<String> newNodeIDList = new ArrayList<String>();
			newNodeIDList.addAll(nodeIDList);
			newNodeIDList.remove(newNodeIDList.indexOf(tmp));

			List<Cluster> ClusterList2 = getPossibleSizedCombination(
					newNodeIDList, size - 1);

			List<String> existingNodeIDList = new ArrayList<String>();
			existingNodeIDList.add(tmp);
			addExistingNodeIDsFor(ClusterList2, existingNodeIDList);

			clusterList.addAll(ClusterList2);
		}
		return clusterList;
	}

	// Evaluate the independency metrics for a give candidate in the graph
	public static float calcIMValueforCandCluster(Cluster candidate,
			DWGraph graph) {
		int clusterSize = candidate.atomicNodeIDList.size();
		float internalValue = 0, externalValue = 0;

		List<Integer> internalIndexs = new ArrayList<Integer>();
		List<Integer> externalIndexs = new ArrayList<Integer>();
		for (int i = 0; i < graph.nodeSize; i++) {
			String nodeID = graph.nodeIDList.get(i);
			int index = candidate.atomicNodeIDList.indexOf(nodeID);
			if (index >= 0) {
				internalIndexs.add(new Integer(i));
			} else {
				externalIndexs.add(i);
			}
		}

		// Calculate the internal value
		for (int i = 0; i < internalIndexs.size(); i++)
			for (int j = 0; j < internalIndexs.size(); j++) {
				if (i != j) {
					internalValue = internalValue
							+ graph.graph[internalIndexs.get(i).intValue()][internalIndexs
									.get(j).intValue()]
							+ graph.graph[internalIndexs.get(j).intValue()][internalIndexs
									.get(i).intValue()];
				}
			}

		for (int i = 0; i < externalIndexs.size(); i++)
			for (int j = 0; j < internalIndexs.size(); j++) {
				externalValue = externalValue
						+ graph.graph[externalIndexs.get(i).intValue()][internalIndexs
								.get(j).intValue()]
						+ graph.graph[internalIndexs.get(j).intValue()][externalIndexs
								.get(i).intValue()];
			}

		float result = (internalValue - externalValue) / clusterSize;

		return result;
	}

	// Check whether one cluster is overlapped with any one cluster in the
	// cluster list
	public static boolean overlapped(List<Cluster> clusterList, Cluster cluster) {
		List<String> nodeIDList = new ArrayList<String>();
		for (Cluster tmp : clusterList) {
			nodeIDList.addAll(tmp.atomicNodeIDList);
		}
		for (String nodeID : cluster.atomicNodeIDList) {
			if (nodeIDList.indexOf(nodeID) >= 0)
				return true;
		}
		return false;
	}

	// Eniminate redundancy
	public static void eniminateDuplica(List<String> nodeIDList) {
		for (int i = 0; i < nodeIDList.size(); i++) {
			String nodeID = nodeIDList.get(i);
			for (int j = i + 1; j < nodeIDList.size(); j++) {
				String nodeID2 = nodeIDList.get(j);
				if (nodeID.equals(nodeID2))
					nodeIDList.remove(j);
			}
		}
	}

	public static float calcWeight(DWGraph oldGraph, Cluster clusterFrom,
			String nodeIDTo) {
		List<Integer> fromNodeIndexList = new ArrayList<Integer>();
		for (String nodeID : clusterFrom.atomicNodeIDList) {
			fromNodeIndexList.add(new Integer(oldGraph.nodeIDList
					.indexOf(nodeID)));
		}
		int toNodeIndex = oldGraph.nodeIDList.indexOf(nodeIDTo);
		float weight = 0;
		for (Integer index : fromNodeIndexList) {
			int iIndex = index.intValue();
			weight = weight + oldGraph.graph[iIndex][toNodeIndex];
		}
		return weight;
	}

	public static float calcWeight(DWGraph oldGraph, String nodeIDFrom,
			Cluster clusterTo) {
		List<Integer> toNodeIndexList = new ArrayList<Integer>();
		for (String nodeID : clusterTo.atomicNodeIDList) {
			toNodeIndexList
					.add(new Integer(oldGraph.nodeIDList.indexOf(nodeID)));
		}
		int fromNodeIndex = oldGraph.nodeIDList.indexOf(nodeIDFrom);
		float weight = 0;
		for (Integer index : toNodeIndexList) {
			int iIndex = index.intValue();
			weight = weight + oldGraph.graph[fromNodeIndex][iIndex];
		}
		return weight;
	}

	public static float calcWeight(DWGraph oldGraph, Cluster clusterFrom,
			Cluster clusterTo) {
		List<Integer> fromNodeIndexList = new ArrayList<Integer>();
		for (String nodeID : clusterFrom.atomicNodeIDList) {
			fromNodeIndexList.add(new Integer(oldGraph.nodeIDList
					.indexOf(nodeID)));
		}
		List<Integer> toNodeIndexList = new ArrayList<Integer>();
		for (String nodeID : clusterTo.atomicNodeIDList) {
			toNodeIndexList
					.add(new Integer(oldGraph.nodeIDList.indexOf(nodeID)));
		}

		float weight = 0;

		for (int i = 0; i < fromNodeIndexList.size(); i++)
			for (int j = 0; j < toNodeIndexList.size(); j++) {
				weight = weight
						+ oldGraph.graph[fromNodeIndexList.get(i).intValue()][toNodeIndexList
								.get(j).intValue()];
			}
		return weight;
	}

	// parse the iterative result as cluster tree
	public static Cluster parse(String result /* Format as (........) */) {
		int start = result.indexOf("(");

		int end = result.lastIndexOf(")");

		Queue<String> queue = new LinkedList<String>();

		int objStart = start + 1;

		Cluster newCluster = new Cluster();

		for (int i = start + 1; i < end; i++) {
			String subStr = result.substring(i, i + 1);
			if (subStr.equals("-") && queue.isEmpty()) {
				if (objStart < i) {
					String nodeID = result.substring(objStart, i);
					newCluster.atomicNodeIDList.add(nodeID);
				}
				objStart = i + 1;
			}

			if (subStr.equals("(")) {
				if (queue.isEmpty()) {
					objStart = i;
					queue.offer("(");
				} else
					queue.offer("(");
			}

			if (subStr.equals(")")) {
				if (queue.size() == 1 && queue.peek().equals("(")) {
					String newStr = result.substring(objStart, i + 1);
					objStart = i + 1;
					Cluster subCluster = parse(newStr);
					newCluster.clusterChildren.add(subCluster);
					subCluster.parent = newCluster;
					queue.poll();
				} else if (queue.size() > 1 && queue.peek().equals("(")) {
					queue.poll();
				}

			}

			if (i == (end - 1) && !subStr.equals(")")) {
				String nodeID = result.substring(objStart, i + 1);
				newCluster.atomicNodeIDList.add(nodeID);
			}

		}

		return newCluster;
	}

	public static String toString(Cluster result) {
		String resultStr = new String();

		int index = 0;
		for (String atomicNodeID : result.atomicNodeIDList) {
			if (index == 0) {
				resultStr = atomicNodeID;
			} else
				resultStr = resultStr + ClusteringUtils.seperator
						+ atomicNodeID;
			index++;
		}

		for (Cluster child : result.clusterChildren) {
			String childStr = toString(child);
			if (resultStr.length() == 0)
				resultStr = childStr;
			else
				resultStr = resultStr + ClusteringUtils.seperator + childStr;
		}

		resultStr = "(" + resultStr + ")";

		return resultStr;
	}

	public static void label(Cluster cluster) {
		int[] marks = new int[26];
		label_helper(cluster, marks, 0);
	}

	private static void label_helper(Cluster root, int[] marks, int depth) {
		char s = (char) ((int) 'A' + depth);
		root.label = s + "_" + marks[depth];
		marks[depth]++;
		for (Cluster child : root.clusterChildren) {
			label_helper(child, marks, depth + 1);
		}
	}

	public static int getGraphClusterNumber(Cluster cluster) {
		if (cluster.clusterChildren.size() == 0) {
			return 1;
		}
		int sum = 0;
		for (Cluster child : cluster.clusterChildren) {
			sum += getGraphClusterNumber(child);
		}
		return sum;
	}
}
